package com.zdp.leetcodeMiddle;


import com.zdp.util.TreeNode;

import java.util.*;

/*
* 题目描述：
* 给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 二叉树的后序遍历_145 {

    private List<Integer> result = new ArrayList<>();
    /*
    * 使用递归完成
    * */
    public List<Integer> postorderTraversal(TreeNode root) {
        f(root);
        return result;
    }
    public void f(TreeNode t){
        if(t== null){
            return ;
        }
        f(t.left);
        f(t.right);
        result.add(t.val);
    }

    /*
    * 使用迭代完成，迭代我感觉可以看着递归来写
    * 使用栈结构 不就可以完成递归操作了嘛
    * */
    public List<Integer> postorderTraversal1(TreeNode root){
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null){
            return result;
        }
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode p = stack.peek();
            if(p.left != null){
                stack.push(p.left);
                p.left = null;
            }else if(p.right != null){
                stack.push(p.right);
                p.right = null;
            }else{
                // 都为空的话
                result.add(stack.pop().val);
            }
        }
        return result;
    }

    /*
    * 官方迭代：
    * */
    public List<Integer> postorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right == prev) {
                res.add(root.val);
                prev = root; // 记录下出栈的那个节点
                // 接下来会回到当前出栈节点的 父亲节点
                // 如果 root.right == prev  说明是回溯上来的
                // 就不要再将root.right 入栈了 避免死循环
                // 跟我的将 p.right 或者 p.left 设置为 null 是一个功能
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }

}
